package com.lisp.algorithm.concurrent;

import java.util.concurrent.atomic.AtomicReference;

public class ConcurrentLinkedQueue<V> {

    private Node DUMMY = new Node(null);
    private AtomicReference<Node> head = new AtomicReference<>(DUMMY);
    private AtomicReference<Node> tail = new AtomicReference<>(DUMMY);
    
    public void put(V v) {
        Node newTail = new Node(v);
        
        Node oldTail = null;
        do {
            oldTail = tail.get();
            AtomicReference<Node> oldTailNext = oldTail.next;
            Node oldTailNextNode = oldTailNext.get();
            if(oldTailNextNode != null) {
                tail.compareAndSet(oldTail, oldTailNextNode);                
            }
        } while(!oldTail.next.compareAndSet(null, newTail));
        tail.compareAndSet(oldTail, newTail);
    }
    
    public V get() {
        Node n = DUMMY.next.get();
        return n == null ? null 
                : n.value;
    }
    
    public V remove() {
        
        Node firstNode = null;
        Node secondNode = null;
        do {
            firstNode = DUMMY.next.get();
            if(firstNode == null) {
                return null;
            }
            secondNode = firstNode.next.get();
            
        } while(!DUMMY.next.compareAndSet(firstNode, secondNode));
        return firstNode.value;
    }
    
    class Node {
        private final V value;
        private AtomicReference<Node> next;
        
        Node(V val) {
            this.value = val;
            this.next = new AtomicReference<>(null);
        }
    }
    
    public static void main(String[] args) {
        final ConcurrentLinkedQueue<Integer> clq = new ConcurrentLinkedQueue<>();
        clq.put(10);
        clq.get();
        TestUtil.test(10, 1000, () -> {
            clq.put(10);
            clq.get();
        });
    }
}
